package BinaryTree;

import java.util.HashMap;
import java.util.Map;
/*
* 重建二叉树
* 分别递归
*       前序左左,中序左左
*       前序右右,中序右右
*  // *********递归终止条件: 左边界大与右边界********
* */
public class Offer07buildTree {
    Map<Integer,Integer> map=new HashMap<Integer,Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n=inorder.length;
        for(int i=0;i<n;i++){
            map.put(inorder[i],i);
        }
        return myBuild(preorder,inorder,0,n-1,0,n-1);
    }

    private TreeNode myBuild(int[] preorder, int[] inorder, int pre_left, int pre_right, int inorder_left, int inorder_right) {
        // 递归终止条件: 左边界打与右边界
        if(pre_left>pre_right){
            return null;
        }
        int inorder_root=map.get(preorder[pre_left]);

        int size_left_subtree=inorder_root-inorder_left;
        //先构造出根节点
        TreeNode root = new TreeNode(preorder[pre_left]);
        root.left=myBuild(preorder,inorder,pre_left+1,pre_left+size_left_subtree,inorder_left,inorder_root-1);
        root.right=myBuild(preorder,inorder,pre_left+size_left_subtree+1,pre_right,inorder_root+1,inorder_right);
        return root;
    }
}
